void mergesort2(index low, index high)
{
  index mid;

  if (low < high) {
    mid = (low + high) / 2;
    mergesort2(low, mid);
    mergesort2(mid+1, high);
    merge2(low, mid, high);
  }
}

void merge2(index low, index mid, index high)
{
  index i, j, k;
  keytype U[low..high]; // A local array needed for the merging

  i = low; j = mid + 1; k = low;
  while (i <= mid && j <= high) {
    if (S[i] < S[j]) {
      U[k] = S[i];
      i++;
    }
    else {
      U[k] = S[j];
      j++;
    }
    k++;
  }
  if (i > mid)
    move S[j] through S[high] to U[k] through U[high];
  else
    move S[i] through S[mid] to U[k] through U[high];
  move U[low] through U[high] to S[low] through S[high];
}

// File: sorting.h
#ifndef SORTING_H
#define SORTING_H

namespace algorithms
{
  void mergesort2(int data[ ], int low, int high);
  // Problem: Sort n keys in nondecreasing sequence.
  // Inputs: positive integer n, array of key S indexed from 1 to n.
  // the array S containing the keys in nondecreasing order.

  void merge2(int data[ ], int low, int mid, int high);
  // Problem: Merge the two sorted subarrays of S created in Mergesort 2.
  // Inputs: indices low, mid, and high, and the subarray of S indexed
  // from low to high. The keys in array slots from low to mid are already
  // sorted in nondecreasing order, as are the keys in array slots from
  // mid +1 to high.
  // Outputs: the subarray of S indexed from low to high containing the
  // keys in nondecreasing order.
}  
#endif

// File: sorting.cpp
namespace algorithms
{
  void mergesort2(int data[ ], int low, int high)
  {
    int mid;

    if (low < high)
    {
      mid = (low + high) / 2;
      mergesort2(data, low, mid);
      mergesort2(data, mid+1, high);
      merge2(data, low, mid, high);
    }
  }

  void merge2(int data[ ], int low, int mid, int high)
  {
    int i, j, k;
    // A local array needed for the merging
    int* temp = new int[(high-low) + 1];

    i = low;
    j = mid + 1;
    k = 0;
    while (i <= mid && j <= high)
    {
      if (data[i] < data[j])
        temp[k] = data[i++]; // Copy from first half
      else
        temp[k] = data[j++]; // Copy from second half
      k++;
    }

    // Copy any remaining entries in the left and right subarrays.
    if (i > mid)
    {
      while (j <= high)
        temp[k++] = data[j++];
    }
    else
    {
      while (i <= mid)
        temp[k++] = data[i++];
    }

    // Copy from temp back to the data array, and release temp's memory.
    i = low;
    for (k = 0; k < (high-low) + 1 ; ++k)
      data[i++] = temp[k];

    delete [ ] temp;
  }
}

// File: sorttest.cpp
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include "sorting.h" // Provides sorting functions.
using namespace std;
using namespace algorithms;

// PROTOTYPE of a function that will test one of the sorting functions:
void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name);

void open_for_read(ifstream& f, const char filename[ ]);
// Postcondition: The ifstream f has been opened for reading using the given
// filename. If any errors occurred then an error message has been printed
// and the program has been halted.

bool is_more(istream& source);
// Precondition: input is an open istream.
// Postcondition: The return value is true if input still has more data to
// read; otherwise the return value is false.

void process_read(ifstream& f, int data[ ]);
// Precondition: input is an open istream.
// Postcondition: The values in inputfile are assigned to data array.

int main(int argc, char* argv[ ])
{  
  assert(argc == 2);
  testsort(mergesort2, argv[1], "mergesort");

  return EXIT_SUCCESS;
}

void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name)
{

  const int ARRAY_SIZE = 100000;
  int data[ARRAY_SIZE];
  ifstream infile;

  open_for_read(infile, file_name);
  process_read(infile, data);
  infile.close( );

  clock_t start, end;  
  cout << "Testing the " << sorting_name << endl;
  start = clock( );
  sorter(data, 0, ARRAY_SIZE-1); // Sort the numbers
  end = clock( );

  // Check the sorting result.
  for (int i = 1; i < ARRAY_SIZE; ++i)
  {
    if (data[i-1] > data[i])
      exit(0);
  }
  cout << "Sorting completed correctly." << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << sorting_name << "'s elpased time is : "<< result << " sec." << endl;
}

void open_for_read(ifstream& f, const char filename[ ])
{
  f.open(filename);

  if (f.fail( ))
  {
    cerr << "Could not open input file." << endl;
    exit(0);
  }
}

bool is_more(ifstream& source)
{
  return (source && source.peek( ) != EOF);
}

void process_read(ifstream& f, int data[ ])
{
  size_t index = 0;

  while (is_more(f))
  {
    assert(f);
    f >> data[index];
    ++index;
  }
}